# K = 8 and d = 4, m = 16, n = 8, C^(A) = r, C^(B) = r
import numpy as np
import time

m = 16
n = 8
CA = 18
CB = 18

# k = 1, d = 1
A_1_1 = np.random.normal(0, 1/np.sqrt(2*np.pi), (m, CA))
B_1_1 = np.random.normal(0, 1/np.sqrt(2*np.pi), (n, CB))

# k = 1, d = 2
A_1_2 = np.random.normal(0, 1/np.sqrt(2*np.pi), (m, CA))
B_1_2 = np.random.normal(0, 1/np.sqrt(2*np.pi), (n, CB))

# k = 1, d = 3
A_1_3 = np.random.normal(0, 1/np.sqrt(2*np.pi), (m, CA))
B_1_3 = np.random.normal(0, 1/np.sqrt(2*np.pi), (n, CB))

# k = 1, d = 4
A_1_4 = np.random.normal(0, 1/np.sqrt(2*np.pi), (m, CA))
B_1_4 = np.random.normal(0, 1/np.sqrt(2*np.pi), (n, CB))

# k = 2, d = 1
A_2_1 = np.random.normal(0, 1/np.sqrt(2*np.pi), (m, CA))
B_2_1 = np.random.normal(0, 1/np.sqrt(2*np.pi), (n, CB))

# k = 2, d = 2
A_2_2 = np.random.normal(0, 1/np.sqrt(2*np.pi), (m, CA))
B_2_2 = np.random.normal(0, 1/np.sqrt(2*np.pi), (n, CB))

# k = 2, d = 3
A_2_3 = np.random.normal(0, 1/np.sqrt(2*np.pi), (m, CA))
B_2_3 = np.random.normal(0, 1/np.sqrt(2*np.pi), (n, CB))

# k = 2, d = 4
A_2_4 = np.random.normal(0, 1/np.sqrt(2*np.pi), (m, CA))
B_2_4 = np.random.normal(0, 1/np.sqrt(2*np.pi), (n, CB))

# k = 3, d = 1
A_3_1 = np.random.normal(0, 1/np.sqrt(2*np.pi), (m, CA))
B_3_1 = np.random.normal(0, 1/np.sqrt(2*np.pi), (n, CB))

# k = 3, d = 2
A_3_2 = np.random.normal(0, 1/np.sqrt(2*np.pi), (m, CA))
B_3_2 = np.random.normal(0, 1/np.sqrt(2*np.pi), (n, CB))

# k = 3, d = 3
A_3_3 = np.random.normal(0, 1/np.sqrt(2*np.pi), (m, CA))
B_3_3 = np.random.normal(0, 1/np.sqrt(2*np.pi), (n, CB))

# k = 3, d = 4
A_3_4 = np.random.normal(0, 1/np.sqrt(2*np.pi), (m, CA))
B_3_4 = np.random.normal(0, 1/np.sqrt(2*np.pi), (n, CB))

# k = 4, d = 1
A_4_1 = np.random.normal(0, 1/np.sqrt(2*np.pi), (m, CA))
B_4_1 = np.random.normal(0, 1/np.sqrt(2*np.pi), (n, CB))

# k = 4, d = 2
A_4_2 = np.random.normal(0, 1/np.sqrt(2*np.pi), (m, CA))
B_4_2 = np.random.normal(0, 1/np.sqrt(2*np.pi), (n, CB))

# k = 4, d = 3
A_4_3 = np.random.normal(0, 1/np.sqrt(2*np.pi), (m, CA))
B_4_3 = np.random.normal(0, 1/np.sqrt(2*np.pi), (n, CB))

# k = 4, d = 4
A_4_4 = np.random.normal(0, 1/np.sqrt(2*np.pi), (m, CA))
B_4_4 = np.random.normal(0, 1/np.sqrt(2*np.pi), (n, CB))

# k = 5, d = 1
A_5_1 = np.random.normal(0, 1/np.sqrt(2*np.pi), (m, CA))
B_5_1 = np.random.normal(0, 1/np.sqrt(2*np.pi), (n, CB))

# k = 5, d = 2
A_5_2 = np.random.normal(0, 1/np.sqrt(2*np.pi), (m, CA))
B_5_2 = np.random.normal(0, 1/np.sqrt(2*np.pi), (n, CB))

# k = 5, d = 3
A_5_3 = np.random.normal(0, 1/np.sqrt(2*np.pi), (m, CA))
B_5_3 = np.random.normal(0, 1/np.sqrt(2*np.pi), (n, CB))

# k = 5, d = 4
A_5_4 = np.random.normal(0, 1/np.sqrt(2*np.pi), (m, CA))
B_5_4 = np.random.normal(0, 1/np.sqrt(2*np.pi), (n, CB))

# k = 6, d = 1
A_6_1 = np.random.normal(0, 1/np.sqrt(2*np.pi), (m, CA))
B_6_1 = np.random.normal(0, 1/np.sqrt(2*np.pi), (n, CB))

# k = 6, d = 2
A_6_2 = np.random.normal(0, 1/np.sqrt(2*np.pi), (m, CA))
B_6_2 = np.random.normal(0, 1/np.sqrt(2*np.pi), (n, CB))

# k = 6, d = 3
A_6_3 = np.random.normal(0, 1/np.sqrt(2*np.pi), (m, CA))
B_6_3 = np.random.normal(0, 1/np.sqrt(2*np.pi), (n, CB))

# k = 6, d = 4
A_6_4 = np.random.normal(0, 1/np.sqrt(2*np.pi), (m, CA))
B_6_4 = np.random.normal(0, 1/np.sqrt(2*np.pi), (n, CB))

# k = 7, d = 1
A_7_1 = np.random.normal(0, 1/np.sqrt(2*np.pi), (m, CA))
B_7_1 = np.random.normal(0, 1/np.sqrt(2*np.pi), (n, CB))

# k = 7, d = 2
A_7_2 = np.random.normal(0, 1/np.sqrt(2*np.pi), (m, CA))
B_7_2 = np.random.normal(0, 1/np.sqrt(2*np.pi), (n, CB))

# k = 7, d = 3
A_7_3 = np.random.normal(0, 1/np.sqrt(2*np.pi), (m, CA))
B_7_3 = np.random.normal(0, 1/np.sqrt(2*np.pi), (n, CB))

# k = 7, d = 4
A_7_4 = np.random.normal(0, 1/np.sqrt(2*np.pi), (m, CA))
B_7_4 = np.random.normal(0, 1/np.sqrt(2*np.pi), (n, CB))

# k = 8, d = 1
A_8_1 = np.random.normal(0, 1/np.sqrt(2*np.pi), (m, CA))
B_8_1 = np.random.normal(0, 1/np.sqrt(2*np.pi), (n, CB))

# k = 8, d = 2
A_8_2 = np.random.normal(0, 1/np.sqrt(2*np.pi), (m, CA))
B_8_2 = np.random.normal(0, 1/np.sqrt(2*np.pi), (n, CB))

# k = 8, d = 3
A_8_3 = np.random.normal(0, 1/np.sqrt(2*np.pi), (m, CA))
B_8_3 = np.random.normal(0, 1/np.sqrt(2*np.pi), (n, CB))

# k = 8, d = 4
A_8_4 = np.random.normal(0, 1/np.sqrt(2*np.pi), (m, CA))
B_8_4 = np.random.normal(0, 1/np.sqrt(2*np.pi), (n, CB))

# x
X = np.random.uniform(0.0, 1.0, (m,m,m,m))

# W
W = np.random.normal(0, 1/np.sqrt(2*np.pi), (m*m*m*m, n*n*n*n))


def normal_algo_1():
	tm_kron = 0
	tm_mat = 0
	tm_trans = 0

	t_all_s = time.time()

	t_kron_s = time.time()
	AB_1_1 = np.kron(A_1_1, B_1_1)
	AB_1_2 = np.kron(A_1_2, B_1_2)
	AB_1_3 = np.kron(A_1_3, B_1_3)
	AB_1_4 = np.kron(A_1_4, B_1_4)
	AB_2_1 = np.kron(A_2_1, B_2_1)
	AB_2_2 = np.kron(A_2_2, B_2_2)
	AB_2_3 = np.kron(A_2_3, B_2_3)
	AB_2_4 = np.kron(A_2_4, B_2_4)
	AB_3_1 = np.kron(A_3_1, B_3_1)
	AB_3_2 = np.kron(A_3_2, B_3_2)
	AB_3_3 = np.kron(A_3_3, B_3_3)
	AB_3_4 = np.kron(A_3_4, B_3_4)
	AB_4_1 = np.kron(A_4_1, B_4_1)
	AB_4_2 = np.kron(A_4_2, B_4_2)
	AB_4_3 = np.kron(A_4_3, B_4_3)
	AB_4_4 = np.kron(A_4_4, B_4_4)
	AB_5_1 = np.kron(A_5_1, B_5_1)
	AB_5_2 = np.kron(A_5_2, B_5_2)
	AB_5_3 = np.kron(A_5_3, B_5_3)
	AB_5_4 = np.kron(A_5_4, B_5_4)
	AB_6_1 = np.kron(A_6_1, B_6_1)
	AB_6_2 = np.kron(A_6_2, B_6_2)
	AB_6_3 = np.kron(A_6_3, B_6_3)
	AB_6_4 = np.kron(A_6_4, B_6_4)
	AB_7_1 = np.kron(A_7_1, B_7_1)
	AB_7_2 = np.kron(A_7_2, B_7_2)
	AB_7_3 = np.kron(A_7_3, B_7_3)
	AB_7_4 = np.kron(A_7_4, B_7_4)
	AB_8_1 = np.kron(A_8_1, B_8_1)
	AB_8_2 = np.kron(A_8_2, B_8_2)
	AB_8_3 = np.kron(A_8_3, B_8_3)
	AB_8_4 = np.kron(A_8_4, B_8_4)
	t_kron_e = time.time()
	tm_kron = tm_kron + (t_kron_e - t_kron_s)

	W_1 = np.concatenate([AB_1_1, AB_2_1, AB_3_1, AB_4_1, AB_5_1, AB_6_1, AB_7_1, AB_8_1], axis = -1)
	W_2 = np.concatenate([AB_1_2, AB_2_2, AB_3_2, AB_4_2, AB_5_2, AB_6_2, AB_7_2, AB_8_2], axis = -1)
	W_3 = np.concatenate([AB_1_3, AB_2_3, AB_3_3, AB_4_3, AB_5_3, AB_6_3, AB_7_3, AB_8_3], axis = -1)
	W_4 = np.concatenate([AB_1_4, AB_2_4, AB_3_4, AB_4_4, AB_5_4, AB_6_4, AB_7_4, AB_8_4], axis = -1)

	# W_1 to (m_1 * n_1*C)
	W_1 = np.reshape(np.reshape(W_1, (m, n, -1)), (m, -1))

	# Y is (m_2*m_3*m_4 * n_1*C)
	t_mat_s = time.time()
	Y = np.matmul(np.reshape(X, (m, m*m*m)).T, W_1)
	t_mat_e = time.time()
	tm_mat = tm_mat + (t_mat_e - t_mat_s)

	# Y to (n_1*m_3*m_4 * m_2*C)
	t_trans_s = time.time()
	Y = np.reshape(Y, (m, m*m, n, -1))
	Y = np.transpose(Y, (2, 1, 0, 3))
	Y = np.reshape(Y, (n*m*m, -1))
	t_trans_e = time.time()
	tm_trans = tm_trans + (t_trans_e - t_trans_s)

	# W_2 to (m_2*C * n_2)
	t_trans_s = time.time()
	W_2 = np.reshape(W_2, (m, n, -1))
	W_2 = np.transpose(W_2, (0, 2, 1))
	W_2 = np.reshape(W_2, (-1, n))
	t_trans_e = time.time()
	tm_trans = tm_trans + (t_trans_e - t_trans_s)

	# Y is (n_1*m_3*m_4 * n_2)
	t_mat_s = time.time()
	Y = np.matmul(Y, W_2)
	t_mat_e = time.time()
	tm_mat = tm_mat + (t_mat_e - t_mat_s)

	# Y to (n_1*n_2*m_4 * m_3)
	t_trans_s = time.time()
	Y = np.reshape(Y, (n, m, m, n))
	Y = np.transpose(Y, (0, 3, 2, 1))
	Y = np.reshape(Y, (n*n*m, m))
	t_trans_e = time.time()
	tm_trans = tm_trans + (t_trans_e - t_trans_s)

	# W_3 to (m_3 * n_3*C)
	W_3 = np.reshape(np.reshape(W_3, (m, n, -1)), (m, -1))

	# Y is (n_1*n_2*m_4 * n_3*C)
	t_mat_s = time.time()
	Y = np.matmul(Y, W_3)
	t_mat_e = time.time()
	tm_mat = tm_mat + (t_mat_e - t_mat_s)

	# Y to (n_1*n_2*n_3 * m_4*C)
	t_trans_s = time.time()
	Y = np.reshape(Y, (n*n, m, n, -1))
	Y = np.transpose(Y, (0, 2, 1, 3))
	Y = np.reshape(Y, (n*n*n, -1))
	t_trans_e = time.time()
	tm_trans = tm_trans + (t_trans_e - t_trans_s)

	# W_4 to (m_4*C * n_4)
	t_trans_s = time.time()
	W_4 = np.reshape(W_4, (m, n, -1))
	W_4 = np.transpose(W_4, (0, 2, 1))
	W_4 = np.reshape(W_4, (-1, n))
	t_trans_e = time.time()
	tm_trans = tm_trans + (t_trans_e - t_trans_s)

	# Y is (n_1*n_2*n_3 * n_4)
	t_mat_s = time.time()
	Y = np.matmul(Y, W_4)
	t_mat_e = time.time()
	tm_mat = tm_mat + (t_mat_e - t_mat_s)

	t_all_e = time.time()

	print('Algorithm 1, whole time is (%lf):' % ((t_all_e - t_all_s) * 1000))
	print('Algorithm 1, Kronecker time is (%lf):' % (tm_kron * 1000))
	print('Algorithm 1, contraction time is (%lf):' % (tm_mat * 1000))
	print('Algorithm 1, transpositon time is (%lf):' % (tm_trans * 1000))

	return np.reshape(Y, (-1))


def divided_algo_2():
	def single_algo_2(I, A_1, B_1, A_2, B_2, kron, mat, trans):
		# O is (m_2*m_3*m_4 * C_A)
		t_mat_s = time.time()
		O = np.matmul(np.reshape(I, (m, m*m*m)).T, A_1)
		t_mat_e = time.time()
		mat = mat + (t_mat_e - t_mat_s)

		# O is (m_2*m_3*m_4*n_1 * C_A*C_B)
		t_kron_s = time.time()
		O = np.kron(O, B_1)
		t_kron_e = time.time()
		kron = kron + (t_kron_e - t_kron_s)

		# O is (n_1*m_3*m_4*C_B * m_2*C_A)
		t_trans_s = time.time()
		O = np.reshape(O, (m, -1, n, CA, CB))
		O = np.transpose(O, (2, 1, 4, 0, 3))
		O = np.reshape(O, (-1, m*CA))
		t_trans_e = time.time()
		trans = trans + (t_trans_e - t_trans_s)

		# O is (n_1*m_3*m_4 * C_B)
		t_mat_s = time.time()
		O = np.matmul(O, np.reshape(A_2, (-1)))
		O = np.reshape(O, (-1, CB))
		t_mat_e = time.time()
		mat = mat + (t_mat_e - t_mat_s)

		# O is (n_1*n_2*m_3*m_4)
		t_mat_s = time.time()
		O = np.matmul(O, B_2.T)
		t_mat_e = time.time()
		mat = mat + (t_mat_e - t_mat_s)

		t_trans_s = time.time()
		O = np.reshape(O, (n, -1, n))
		O = np.reshape(np.transpose(O, (0, 2, 1)), (-1))
		t_trans_e = time.time()
		trans = trans + (t_trans_e - t_trans_s)

		return O, kron, mat, trans

	def single_algo_2_2(O, A_3, B_3, A_4, B_4, kron, mat, trans):
		# O to (n_1*n_2*m_4 * m_3)
		t_trans_s = time.time()
		O = np.reshape(O, (-1, m, m))
		O = np.reshape(np.transpose(O, (0, 2, 1)), (-1, m))
		t_trans_e = time.time()
		trans = trans + (t_trans_e - t_trans_s)

		# O is (n_1*n_2*m_4 * C_A)
		t_mat_s = time.time()
		O = np.matmul(O, A_3)
		t_mat_e = time.time()
		mat = mat + (t_mat_e - t_mat_s)

		# O is (n_1*n_2*m_4*n_3 * C_A*C_B)
		t_kron_s = time.time()
		O = np.kron(O, B_3)
		t_kron_e = time.time()
		kron = kron + (t_kron_e - t_kron_s)

		# O is (n_1*n_2*n_3*C_B * m_4*C_A)
		t_trans_s = time.time()
		O = np.reshape(O, (-1, m, n, CA, CB))
		O = np.transpose(O, (0, 2, 4, 1, 3))
		O = np.reshape(O, (-1, m*CA))
		t_trans_e = time.time()
		trans = trans + (t_trans_e - t_trans_s)

		# O is (n_1*n_2*n_3 * C_B)
		t_mat_s = time.time()
		O = np.matmul(O, np.reshape(A_4, (-1)))
		O = np.reshape(O, (-1, CB))
		t_mat_e = time.time()
		mat = mat + (t_mat_e - t_mat_s)

		# O is (n_1*n_2*n_3*n_4)
		t_mat_s = time.time()
		O = np.matmul(O, B_4.T)
		O = np.reshape(O, (-1))
		t_mat_e = time.time()
		mat = mat + (t_mat_e - t_mat_s)
		
		return O, kron, mat, trans

	tm_kron = 0
	tm_mat = 0
	tm_trans = 0

	t_all_s = time.time()
	
	X_1, tm_kron, tm_mat, tm_trans = single_algo_2(X, A_1_1, B_1_1, A_1_2, B_1_2, tm_kron, tm_mat, tm_trans)
	X_2, tm_kron, tm_mat, tm_trans = single_algo_2(X, A_2_1, B_2_1, A_2_2, B_2_2, tm_kron, tm_mat, tm_trans)
	X_3, tm_kron, tm_mat, tm_trans = single_algo_2(X, A_3_1, B_3_1, A_3_2, B_3_2, tm_kron, tm_mat, tm_trans)
	X_4, tm_kron, tm_mat, tm_trans = single_algo_2(X, A_4_1, B_4_1, A_4_2, B_4_2, tm_kron, tm_mat, tm_trans)
	X_5, tm_kron, tm_mat, tm_trans = single_algo_2(X, A_5_1, B_5_1, A_5_2, B_5_2, tm_kron, tm_mat, tm_trans)
	X_6, tm_kron, tm_mat, tm_trans = single_algo_2(X, A_6_1, B_6_1, A_6_2, B_6_2, tm_kron, tm_mat, tm_trans)
	X_7, tm_kron, tm_mat, tm_trans = single_algo_2(X, A_7_1, B_7_1, A_7_2, B_7_2, tm_kron, tm_mat, tm_trans)
	X_8, tm_kron, tm_mat, tm_trans = single_algo_2(X, A_8_1, B_8_1, A_8_2, B_8_2, tm_kron, tm_mat, tm_trans)
	Y = X_1 + X_2 + X_3 + X_4 + X_5 + X_6 + X_7 + X_8

	X_1, tm_kron, tm_mat, tm_trans = single_algo_2_2(Y, A_1_3, B_1_3, A_1_4, B_1_4, tm_kron, tm_mat, tm_trans)
	X_2, tm_kron, tm_mat, tm_trans = single_algo_2_2(Y, A_2_3, B_2_3, A_2_4, B_2_4, tm_kron, tm_mat, tm_trans)
	X_3, tm_kron, tm_mat, tm_trans = single_algo_2_2(Y, A_3_3, B_3_3, A_3_4, B_3_4, tm_kron, tm_mat, tm_trans)
	X_4, tm_kron, tm_mat, tm_trans = single_algo_2_2(Y, A_4_3, B_4_3, A_4_4, B_4_4, tm_kron, tm_mat, tm_trans)
	X_5, tm_kron, tm_mat, tm_trans = single_algo_2_2(Y, A_5_3, B_5_3, A_5_4, B_5_4, tm_kron, tm_mat, tm_trans)
	X_6, tm_kron, tm_mat, tm_trans = single_algo_2_2(Y, A_6_3, B_6_3, A_6_4, B_6_4, tm_kron, tm_mat, tm_trans)
	X_7, tm_kron, tm_mat, tm_trans = single_algo_2_2(Y, A_7_3, B_7_3, A_7_4, B_7_4, tm_kron, tm_mat, tm_trans)
	X_8, tm_kron, tm_mat, tm_trans = single_algo_2_2(Y, A_8_3, B_8_3, A_8_4, B_8_4, tm_kron, tm_mat, tm_trans)
	Y = X_1 + X_2 + X_3 + X_4 + X_5 + X_6 + X_7 + X_8

	t_all_e = time.time()

	print('Algorithm 2, whole time is (%lf):' % ((t_all_e - t_all_s) * 1000))
	print('Algorithm 2, Kronecker time is (%lf):' % (tm_kron * 1000))
	print('Algorithm 2, contraction time is (%lf):' % (tm_mat * 1000))
	print('Algorithm 2, transpositon time is (%lf):' % (tm_trans * 1000))

	return Y


def divided_algo_new1_notransp():
	# A is (m_1*m_2) B is (n_1*n_2)
	def single_algo_1(I, A, B, kron, mat, trans):
		# O is (m_3*m_4)
		t_mat_s = time.time()
		O = np.matmul(np.reshape(A, (-1)), np.reshape(I, (m*m, -1)))
		t_mat_e = time.time()
		mat = mat + (t_mat_e - t_mat_s)

		# O is (m_3*m_4 * n_1*n_2)
		t_kron_s = time.time()
		O = np.outer(O, np.reshape(B, (-1)))
		t_kron_e = time.time()
		kron = kron + (t_kron_e - t_kron_s)

		return O, kron, mat, trans

	# A is (m_3*m_4) B is (n_3*n_4)
	def single_algo_1_2(O, A, B, kron, mat, trans):
		# O is (n_1*n_2)
		t_mat_s = time.time()
		O = np.matmul(np.reshape(A, (-1)), O)
		t_mat_e = time.time()
		mat = mat + (t_mat_e - t_mat_s)

		# O is (n_1*n_2 * n_3*n_4)
		t_kron_s = time.time()
		O = np.outer(O, np.reshape(B, (-1)))
		t_kron_e = time.time()
		kron = kron + (t_kron_e - t_kron_s)

		return np.reshape(O, (-1)), kron, mat, trans

	
	tm_kron = 0
	tm_mat = 0
	tm_trans = 0

	t_all_s = time.time()
	
	t_mat_s = time.time()
	# k = 1
	A_1_12 = np.matmul(A_1_1, A_1_2.T)
	B_1_12 = np.matmul(B_1_1, B_1_2.T)
	A_1_34 = np.matmul(A_1_3, A_1_4.T)
	B_1_34 = np.matmul(B_1_3, B_1_4.T)

	# k = 2
	A_2_12 = np.matmul(A_2_1, A_2_2.T)
	B_2_12 = np.matmul(B_2_1, B_2_2.T)
	A_2_34 = np.matmul(A_2_3, A_2_4.T)
	B_2_34 = np.matmul(B_2_3, B_2_4.T)

	# k = 3
	A_3_12 = np.matmul(A_3_1, A_3_2.T)
	B_3_12 = np.matmul(B_3_1, B_3_2.T)
	A_3_34 = np.matmul(A_3_3, A_3_4.T)
	B_3_34 = np.matmul(B_3_3, B_3_4.T)

	# k = 4
	A_4_12 = np.matmul(A_4_1, A_4_2.T)
	B_4_12 = np.matmul(B_3_1, B_4_2.T)
	A_4_34 = np.matmul(A_4_3, A_4_4.T)
	B_4_34 = np.matmul(B_4_3, B_4_4.T)

	# k = 5
	A_5_12 = np.matmul(A_5_1, A_5_2.T)
	B_5_12 = np.matmul(B_5_1, B_5_2.T)
	A_5_34 = np.matmul(A_5_3, A_5_4.T)
	B_5_34 = np.matmul(B_5_3, B_5_4.T)

	# k = 6
	A_6_12 = np.matmul(A_6_1, A_6_2.T)
	B_6_12 = np.matmul(B_6_1, B_6_2.T)
	A_6_34 = np.matmul(A_6_3, A_6_4.T)
	B_6_34 = np.matmul(B_6_3, B_6_4.T)

	# k = 7
	A_7_12 = np.matmul(A_7_1, A_7_2.T)
	B_7_12 = np.matmul(B_7_1, B_7_2.T)
	A_7_34 = np.matmul(A_7_3, A_7_4.T)
	B_7_34 = np.matmul(B_7_3, B_7_4.T)

	# k = 8
	A_8_12 = np.matmul(A_8_1, A_8_2.T)
	B_8_12 = np.matmul(B_8_1, B_8_2.T)
	A_8_34 = np.matmul(A_8_3, A_8_4.T)
	B_8_34 = np.matmul(B_8_3, B_8_4.T)
	t_mat_e = time.time()
	tm_mat = tm_mat + (t_mat_e - t_mat_s)

	X_1, tm_kron, tm_mat, tm_trans = single_algo_1(X, A_1_12, B_1_12, tm_kron, tm_mat, tm_trans)
	X_2, tm_kron, tm_mat, tm_trans = single_algo_1(X, A_2_12, B_2_12, tm_kron, tm_mat, tm_trans)
	X_3, tm_kron, tm_mat, tm_trans = single_algo_1(X, A_3_12, B_3_12, tm_kron, tm_mat, tm_trans)
	X_4, tm_kron, tm_mat, tm_trans = single_algo_1(X, A_4_12, B_4_12, tm_kron, tm_mat, tm_trans)
	X_5, tm_kron, tm_mat, tm_trans = single_algo_1(X, A_5_12, B_5_12, tm_kron, tm_mat, tm_trans)
	X_6, tm_kron, tm_mat, tm_trans = single_algo_1(X, A_6_12, B_6_12, tm_kron, tm_mat, tm_trans)
	X_7, tm_kron, tm_mat, tm_trans = single_algo_1(X, A_7_12, B_7_12, tm_kron, tm_mat, tm_trans)
	X_8, tm_kron, tm_mat, tm_trans = single_algo_1(X, A_8_12, B_8_12, tm_kron, tm_mat, tm_trans)
	Y = X_1 + X_2 + X_3 + X_4 + X_5 + X_6 + X_7 + X_8

	X_1, tm_kron, tm_mat, tm_trans = single_algo_1_2(Y, A_1_34, B_1_34, tm_kron, tm_mat, tm_trans)
	X_2, tm_kron, tm_mat, tm_trans = single_algo_1_2(Y, A_2_34, B_2_34, tm_kron, tm_mat, tm_trans)
	X_3, tm_kron, tm_mat, tm_trans = single_algo_1_2(Y, A_3_34, B_3_34, tm_kron, tm_mat, tm_trans)
	X_4, tm_kron, tm_mat, tm_trans = single_algo_1_2(Y, A_4_34, B_4_34, tm_kron, tm_mat, tm_trans)
	X_5, tm_kron, tm_mat, tm_trans = single_algo_1_2(Y, A_5_34, B_5_34, tm_kron, tm_mat, tm_trans)
	X_6, tm_kron, tm_mat, tm_trans = single_algo_1_2(Y, A_6_34, B_6_34, tm_kron, tm_mat, tm_trans)
	X_7, tm_kron, tm_mat, tm_trans = single_algo_1_2(Y, A_7_34, B_7_34, tm_kron, tm_mat, tm_trans)
	X_8, tm_kron, tm_mat, tm_trans = single_algo_1_2(Y, A_8_34, B_8_34, tm_kron, tm_mat, tm_trans)
	Y = X_1 + X_2 + X_3 + X_4 + X_5 + X_6 + X_7 + X_8

	t_all_e = time.time()

	print('Algorithm 3, whole time is (%lf):' % ((t_all_e - t_all_s) * 1000))
	print('Algorithm 3, Kronecker time is (%lf):' % (tm_kron * 1000))
	print('Algorithm 3, contraction time is (%lf):' % (tm_mat * 1000))
	print('Algorithm 3, transpositon time is (%lf):' % (tm_trans * 1000))

	return Y


if __name__ == '__main__':
	Y_1 = normal_algo_1()
	Y_3 = divided_algo_2()
	Y_6 = divided_algo_new1_notransp()
